package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC460 {
    public long startExecuteTime = System.currentTimeMillis();


    class LFUCache {

        int capacity;
        long timeSlot = 0;

        Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
        Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
        Map<Integer, Long> timeSlotMap = new HashMap<>();
        Map<Integer, Set<Integer>> freKeyListMap = new TreeMap<>();

        public LFUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            ++timeSlot;
            if (valMap.containsKey(key)) {
                int curFrequency = frequencyMap.get(key) + 1;
                frequencyMap.put(key, curFrequency);
                timeSlotMap.put(key, timeSlot);
                updateFreKey(key, curFrequency);
//                System.out.println("get: " + valMap.get(key));
                return valMap.get(key);
            }

//            System.out.println("get: -1");
            return -1;
        }

        public void updateFreKey(int key, int curFrequency) {
            int oldFrequency = curFrequency - 1;
            Set<Integer> oldKeySet = freKeyListMap.get(oldFrequency);
            Set<Integer> currentKeySet = freKeyListMap.get(curFrequency);

            if (null != oldKeySet) {
                oldKeySet.remove(key);
                if (oldKeySet.size() <= 0) freKeyListMap.remove(oldFrequency);
            }
            if (null == currentKeySet) currentKeySet = new HashSet<>();
            currentKeySet.add(key);
            freKeyListMap.put(curFrequency, currentKeySet);
        }

        public void put(int key, int value) {
            if (capacity <= 0) return;

            ++timeSlot;
            if (valMap.containsKey(key) || valMap.size() < capacity) {
                frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
                valMap.put(key, value);
                timeSlotMap.put(key, timeSlot);
                updateFreKey(key, frequencyMap.get(key));
            } else {
                //valMap 没有key，需要淘汰
                Set<Integer> eliminateCandidateSet = (Set<Integer>) (freKeyListMap.values().toArray()[0]);
                Map<Long, Set<Integer>> slotKeyMap = new TreeMap<>();

                for (Integer eliminateKey : eliminateCandidateSet) {
                    Long slot = timeSlotMap.get(eliminateKey);
                    if (slotKeyMap.containsKey(slot)) {
                        slotKeyMap.get(slot).add(eliminateKey);
                    } else {
                        Set<Integer> set = new HashSet<>();
                        set.add(eliminateKey);
                        slotKeyMap.put(slot, set);
                    }
                }

                Set<Integer> toEliminateSet = (Set<Integer>) (slotKeyMap.values().toArray()[0]);
                for (Integer ek : toEliminateSet) {
                    valMap.remove(ek);
                    int fre = frequencyMap.get(ek);
                    frequencyMap.remove(ek);
                    timeSlotMap.remove(ek);
                    freKeyListMap.get(fre).remove(ek);
                    if (freKeyListMap.get(fre).size() <= 0) freKeyListMap.remove(fre);
                }

                //添加新值
                frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
                valMap.put(key, value);
                timeSlotMap.put(key, timeSlot);
                updateFreKey(key, frequencyMap.get(key));
            }
        }
    }

    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */

    public void run() {
        LFUCache solution = new LFUCache(0);
        solution.put(1, 1);
        solution.get(1);


//        LFUCache lFUCache = new LFUCache(2);
//        lFUCache.put(1, 1);
//        lFUCache.put(2, 2);
//        lFUCache.get(1);      // 返回 1
//        lFUCache.put(3, 3);   // 去除键 2
//        lFUCache.get(2);      // 返回 -1（未找到）
//        lFUCache.get(3);      // 返回 3
//        lFUCache.put(4, 4);   // 去除键 1
//        lFUCache.get(1);      // 返回 -1（未找到）
//        lFUCache.get(3);      // 返回 3
//        lFUCache.get(4);      // 返回 4
    }

    public static void main(String[] args) throws Exception {
        LC460 an = new LC460();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
